package oj;

import java.util.ArrayList;
import java.util.List;

public class LC22 {
    //倒着减括号的数量
    public List<String> generateParenthesis(int n) {
        List<String> list=new ArrayList<>();
        if(n==0) return list;
        dfs(list,new StringBuilder(),n,n);
        return list;
    }
    private void dfs(List<String> list,StringBuilder path,int left,int right){
        if(left<0 || right<0){
            return;
        }
        if(right<left) return;

        if(left==0 && right==0){
            list.add(path.toString());
            return;
        }

        path.append("(");
        dfs(list,path,left-1,right);
        path.deleteCharAt(path.length()-1);

        path.append(")");
        dfs(list,path,left,right-1);
        path.deleteCharAt(path.length()-1);
    }


    //正着数括号的数量
//    public List<String> generateParenthesis(int n) {
//        List<String> list=new ArrayList<>();
//        dfs(list,0,0,new StringBuilder(),n);
//        return list;
//    }
//    private void dfs(List<String> list,int open,int close,StringBuilder curLen,int max){
//        if(curLen.length()==max*2){
//            list.add(curLen.toString());
//            return;
//        }
//        if(open<max){
//            curLen.append("(");
//            dfs(list,open+1,close,curLen,max);
//            curLen.deleteCharAt(curLen.length()-1);
//        }
//        if(close<open){
//            curLen.append(")");
//            dfs(list,open,close+1,curLen,max);
//            curLen.deleteCharAt(curLen.length()-1);
//        }
//    }
}
